package com.lihepeng.leecode.linkedList;

/**
 * 反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *
 */
public class Solution206 {
    /**
     * 翻转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head ==null) {
            return null;
        }
        ListNode prev =null;
        ListNode cur = head;
        while (cur !=null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return  cur;
    }

    /**
     * 使用递归方案来实现
     *
     * @param head
     * @return
     */
    public ListNode reverseList01(ListNode head) {
        if (head ==null || head.next ==null) {
            return head;
        }
        ListNode newHead = reverseList01(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    /**
     * 翻转链表的前 N 个节点
     *
     * @param head
     * @param n
     * @return
     */
    ListNode successNode = null;
    public ListNode reverseListN(ListNode head,int n){
        if (n ==1) {
            successNode = head.next;
            return head;
        }
        ListNode newHead = reverseListN(head, n - 1);
        head.next.next = head;
        head.next = successNode;
        return newHead;
    }






}
